#include <stdio.h>

#include <stdlib.h>


#define elemType int							/* 链栈元素数据类型，以整型为例 */

#define SNODE_SIZE sizeof (struct sNode)		/* 链栈结点空间大小 */


#define status int	/* 状态型变量 */

#define OVERFLOW -1	/* 内存溢出状态码 */

#define ERROR 0		/* 错误状态码 */

#define OK 1		/* 正确状态码 */


/* 链栈结点存储结构 */

typedef struct sNode {

	elemType data;

	struct sNode *next;

} sNode, *sNodePtr;


/* 链栈存储结构 */

typedef struct linkStack {

	sNodePtr top; /* 栈顶指针 */

} linkStack;


/* 初始化 */

/* 操作结果：构造一个带头结点的空链栈S */

void initStack (linkStack *S) {

	S->top = (sNodePtr) malloc (SNODE_SIZE); /* 产生头结点，栈顶指针指向此头结点 */

	if (!S->top) /* 内存分配失败 */

		exit (OVERFLOW);

	S->top->next = NULL;

}


/* 销毁 */

/* 初始条件：链栈S已存在。操作结果：销毁链栈S */

void destroyStack (linkStack *S) {

	sNodePtr p, q;

	

	p = S->top; /* p指向S的头结点 */

	while (p) {

		q = p->next; /* q指向p的下一个结点 */

		free (p); /* 回收p指向的结点 */

		p = q; /* p移动到下一个结点 */

	} /* 直到没有下一个结点 */

}


/* 清空 */

/* 初始条件：链栈S已存在。操作结果：将S重置为空栈 */

void clearStack (linkStack *S) {

	sNodePtr p, q;

	

	p = S->top->next; /* p指向栈的第一个结点 */

	while (p) {

		q = p->next; /* q指向p的下一个结点 */

		free (p); /* 回收p指向的结点 */

		p = q; /* p移动到下一个结点 */

	}  /* 直到没有下一个结点 */

	

	S->top->next = NULL;

}


/* 判断链栈是否为空 */

/* 初始条件：链栈S已存在。操作结果：若S为空链栈，则返回TRUE，否则返回FALSE */

status stackIsEmpty (linkStack *S) {

	return S->top->next == NULL;

}


/* 求链栈长度 */

/* 初始条件：链栈S已存在。操作结果：返回S中数据元素个数 */

int stackLength (linkStack *S) {

    int i = 0;

    sNodePtr p;

	

	p = S->top->next; /* p指向栈的第一个结点 */

	while (p) { /* 未到栈尾 */

		i++;

		p = p->next;

    }

    

    return i;

}


/* 获取栈顶元素 */

/* 初始条件：链栈S已存在。操作结果：当栈不为空时，将栈顶元素其值赋给e并返回OK，否则返回ERROR */

status getTopElem (linkStack *S, elemType *e) {

	sNodePtr p;

	

	if (stackIsEmpty (S))

		return ERROR;

	

	p = S->top->next; /* p指向栈的第一个结点 */

	*e = p->data;

	

	return OK;

}


/* 入栈 */

/* 操作结果：在S的栈顶插入新的元素e */

status push (linkStack *S, elemType e) {

	sNodePtr p;

	

	p = (sNodePtr) malloc (SNODE_SIZE); /* 产生新结点 */

	if (!p) /* 内存分配失败 */

		exit (OVERFLOW);

	

	p->data = e;

	p->next = S->top->next; /* 将新结点链接到原栈顶 */

	S->top->next = p; /* 栈顶指向新结点 */

    return OK;

}


/* 出栈 */

/* 操作结果：删除S的栈顶元素，并由e返回其值 */

status pop (linkStack *S, elemType *e) {

	sNodePtr p;

	

	if (stackIsEmpty (S))

		return ERROR;

	

	p = S->top->next; /* p指向链栈的第一个结点 */

	*e = p->data; /* 取出数据 */

	S->top->next = p->next;

	free (p); /* 删除该结点 */

	

    if (S->top == p) /* 栈为空 */

    	S->top->next = NULL;

    

    return 1;

}


/* 打印栈内容 */

/* 初始条件：链栈S已存在。操作结果：当栈不为空时，打印栈内容并返回OK，否则返回ERROR */

status printStack (linkStack *S) {

	sNodePtr p;

	

	if (stackIsEmpty (S))

		return ERROR;

	

	p = S->top->next;

	while (p) {

		printf ("%d\t", p->data);

		p = p->next;

	}

	putchar ('\n');

	

	return OK;

}

int main(){
    linkStack *S; 
    initStack(S);
    push(S,1);
    push(S,2);
    printStack(S);
    printf("end\n");
    return 0;
}